#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<int> queens(n);
    vector<int> col(n), diag1(n * 2 - 1), diag2(n * 2 - 1);
    auto dfs = [&](auto&& dfs, int r)
    {
        if (r == n)
        {
            vector<string> cur(n);
            for (int i = 0; i < n; i++)
                cur[i] = string(queens[i], '.') + 'Q' + string(n - 1 - queens[i], '.');
            res.push_back(cur);
            return;
        }

        for (int c = 0; c < n; c++)
        {
            int rc = r - c + n - 1;
            if (!col[c] && !diag1[r + c] && !diag2[rc])
            {
                queens[r] = c;
                col[c] = diag1[r + c] = diag2[rc] = true;
                dfs(dfs, r + 1);
                col[c] = diag1[r + c] = diag2[rc] = false;
            }
        }
    };

    dfs(dfs, 0);
    return res;
}